package com.study.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author tanglingyu
 * @Date: 2021/08/02/ 13:30
 * @Description:初级算法之字符串
 */
public class BaseStringAlgorithm {

  public static void main(String[] args) {
    reverseString(new String[]{"h", "e", "l", "l", "o"});
    reverse(120);
    firstUniqChar("loveleetcode");
    isAnagram("anagram", "nagaram");
    System.out.println(isMatch("abccba", new String[]{"汤", "凌", "宇", "宇", "凌", "汤"}));
    isPalindrome("A man, a plan, a canal: Panama");
  }

  private static boolean isMatch(String match, String[] sources) {
    if (match.length() != sources.length) {
      return false;
    }
    final char[] chars = match.toCharArray();
    Map<Character, String> map = new HashMap<>();
    for (int i = 0; i < chars.length; i++) {
      if (!map.containsKey(chars[i])) {
        map.put(chars[i], sources[i]);
      } else {
        if (!sources[i].equals(map.get(chars[i]))) {
          return false;
        }
      }
    }
    return true;
  }

  private static void reverseString(String[] array) {
    //反转字符串 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhbqj/
    int i = 0;
    int j = array.length - 1;
    while (i < j) {
      String temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      i++;
      j--;
    }
  }

  private static int reverse(int x) {
    //整数反转 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnx13t/
    int res = 0;
    while (x != 0) {
      int t = x % 10;
      int newRes = res * 10 + t;
      //如果数字溢出，直接返回0
      if ((newRes - t) / 10 != res) {
        return 0;
      }
      res = newRes;
      x = x / 10;
    }
    return res;
  }

  private static int firstUniqChar(String s) {
    //字符串中的第一个唯一字符 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn5z8r/
    int count[] = new int[26];
    char[] chars = s.toCharArray();
    //先统计每个字符出现的次数
    for (int i = 0; i < s.length(); i++) {
      count[chars[i] - 'a']++;
    }
    //然后在遍历字符串s中的字符，如果出现次数是1就直接返回
    for (int i = 0; i < s.length(); i++) {
      if (count[chars[i] - 'a'] == 1) {
        return i;
      }
    }
    return -1;
  }

  private static boolean isAnagram(String s, String t) {
    //有效的字母异位词 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn96us/
    if (s.length() != t.length()) {
      return false;
    }
    char[] cs = s.toCharArray();
    char[] ct = t.toCharArray();
    int[] map = new int[26];
    int count = 0;
    for (int i = 0; i < cs.length; i++) {
      //出现了一个新的字符
      if (++map[cs[i] - 'a'] == 1) {
        count++;
      }
      //消失了一个新的字符
      if (--map[ct[i] - 'a'] == 0) {
        count--;
      }
    }
    return count == 0;
  }

  public static boolean isPalindrome(String s) {
    //验证回文串 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xne8id/
    if (s == null || s.length() == 0) {
      return true;
    }
    s = s.toLowerCase();
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
      while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
        i++;
      }
      while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
        j--;
      }
      if (s.charAt(i) != s.charAt(j)) {
        return false;
      }
    }
    return true;
  }

  public static int myAtoi(String str) {
    //字符串转换整数 (atoi) https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnoilh/
    str = str.trim();//去掉前后的空格
    //如果为空，直接返回0
    if (str.length() == 0) {
      return 0;
    }
    int index = 0;//遍历字符串中字符的位置
    int res = 0;//最终结果
    int sign = 1;//符号，1是正数，-1是负数，默认为正数
    int length = str.length();
    //判断符号
    if (str.charAt(index) == '-' || str.charAt(index) == '+') {
      sign = str.charAt(index++) == '+' ? 1 : -1;
    }
    for (; index < length; ++index) {
      //取出字符串中字符，然后转化为数字
      int digit = str.charAt(index) - '0';
      //按照题中的要求，读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。
      //字符串的其余部分将被忽略。如果读取了非数字，后面的都要忽略
      if (digit < 0 || digit > 9) {
        break;
      }
      //越界处理
      if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10
          && digit > Integer.MAX_VALUE % 10)) {
        return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
      } else {
        res = res * 10 + digit;
      }
    }
    return sign * res;
  }
}
